Priority Queue
Priority Queue is an ADT that the item in it will be sorted in given priority. Basically, there are 3 operation of a priority queue where we can insert, find the max priority item and extract the max priority queue.
Insert(PQ, x, priority): Add x into PQ with the priority queue PQ
FindMax(PQ): Return the item in PQ with the highest priority
ExtractMax(PQ): Remove and return an item from PQ with the highest priority.
Implement
The easiest implement of a priority queue we can just simply use the heap. See more about heap.
Worst-Case Time complexity
| Operation | Time Complexity |
|---|---|
| Insert | O(log n) |
| FindMax | O(1) |
| ExtractMax | O(log n) |